package com.kevinkk.dp;

/**
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */

public class BestTimeToBuyAndSellStockIII {
    class Solution {
        public int maxProfit(int[] prices) {
            int length = prices.length;
            int[][] dp = new int[length][4];
            dp[0][0] = -prices[0];  // 第一次持有
            dp[0][1] = 0;           // 第一次不持有
            dp[0][2] = -prices[0];  // 第二次持有
            dp[0][3] = 0;           // 第二次不持有

            for (int i = 1; i < length; i++) {
                dp[i][0] = max(dp[i - 1][0], -prices[i]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
                dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
            }

            return max(dp[length - 1][0], dp[length - 1][1], dp[length - 1][2], dp[length - 1][3]);
        }

        private int max(int... values) {
            int res = Integer.MIN_VALUE;
            for (int i : values)
                res = Math.max(res, i);
            return res;
        }
    }
}
